package mao.leetcode.offer;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Totoro
 * @date 2020/8/14
 * @explain:  使用单调递减队列完成此题。
 */
public class offer59_2 {

    class MaxQueue {
        LinkedList<Integer> maxQ;
        Queue<Integer> queue;

        public MaxQueue() {
            maxQ = new LinkedList<>();
            queue = new LinkedList<>();

        }

        public int max_value() {
            if (maxQ.size() == 0) return -1;
            return maxQ.peekFirst();

        }

        public void push_back(int value) {
            queue.offer(value);
            if (maxQ.size() == 0 ){
                maxQ.offerLast(value);
            }else{
                while(maxQ.size() != 0 && maxQ.peekLast() < value){
                    maxQ.pollLast();
                }
                maxQ.offerLast(value);
            }

        }

        public int pop_front() {
            if(queue.size() == 0) return -1;
            int value = queue.poll();
            if (value == maxQ.peekFirst()){
                maxQ.pop();
            }
            return value;

        }
    }


}
